/*
https://leetcode-cn.com/problems/maximum-gap/solution/zui-da-jian-ju-by-leetcode-solution/
 */
import java.util.Arrays;

public class Solution164 {
    public int maximumGap(int[] nums) {
        if (nums.length<2){
            return 0;
        }
        int min=Arrays.stream(nums).min().getAsInt();
        int max=Arrays.stream(nums).max().getAsInt();
        int d=Math.max((max-min)/(nums.length-1),1);
        int size=(max-min)/d+1;
        int[][] bucket=new int[size][2];
        for (int[] ints : bucket) {
            Arrays.fill(ints,-1);
        }
        for (int i=0;i<nums.length;i++){
            int t=(nums[i]-min)/d;
            if (bucket[t][0]==-1){
                bucket[t][0]=bucket[t][1]=nums[i];
            }else{
                bucket[t][0]=Math.min(bucket[t][0],nums[i]);
                bucket[t][1]=Math.max(bucket[t][1],nums[i]);
            }
        }
        int ans=0,pre=-1;
        for (int i=0;i<size;i++){
            if (bucket[i][0]==-1){
                continue;
            }else{
                if (pre!=-1){
                    ans=Math.max(ans,bucket[i][0]-pre);
                }
                pre=bucket[i][1];
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution164().maximumGap(new int[]{3,6,9,1}));
    }
}
